import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 62536
 * Date: 2024-06-15
 * Time: 9:52
 */
public class Solution {
    //相同的数划为一类求总和，然后转化为打家劫舍问题
    public int deleteAndEarn(int[] nums) {
        Arrays.sort(nums);
        int[] arr = new int[nums[nums.length - 1] + 1];
        for (int num : nums) {
            arr[num] += num;
        }
        int m = arr.length;
        int[] f = new int[m];
        int[] g = new int[m];
        g[0] = 0;

        for (int i = 1; i < m; i++) {
            f[i] = arr[i] + g[i-1];
            g[i] = Math.max(f[i-1], g[i-1]);
        }


        return Math.max(f[m-1], g[m-1]);
    }
}
